struct Solution;

impl Solution{
    //  代码 13-1
    pub fn my_pow(x: f64, n: i32) -> f64{
        let mut x = x;
        let mut n = n;

        if n < 0{
            x = 1.0/x;
            n = -n;
        }

        return fast_pow(x, n);
    }

    // 代码 13-2
    pub fn climb_stairs(n: i32) -> i32{
        let mut memo  = vec![0; n as usize];
        return  recurison(n as usize , &mut memo);
    }
}


fn fast_pow(x: f64, n: i32) -> f64{
    if n == 0{
        return 1.0;
    }

    let half = fast_pow(x, n/2);

    return if n %2 == 0{
        half * half 
    } else{
        half * half *x
    }
}



fn recurison(n: usize, memo: &mut Vec<i32>) -> i32{
    
    // 终止条件 
    if n <= 2{
        return n as i32;
    }

    // 下探到下一层
    if memo[n - 1] == 0{
        memo[n - 1] = recurison(n-1, memo);
    }

    if memo[n - 2] == 0{
        memo[n - 2] = recurison(n-2,memo);
    }

        return memo[n - 1] + memo[n - 2];

}








#[cfg(test)]
mod recutsion_test{

    use super::*;

    #[test]
    fn pow()
    {
        println!("2^30 = {}",Solution::my_pow(2.0,30));
        println!("2^31 = {}",Solution::my_pow(2.0,31));
    }

    #[test]
    fn climb_staire()
    {
        let a = Solution::climb_stairs(4);
        println!("{}",a);
    }


}

